{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "google",
   "metadata": {},
   "source": [
    "##### Copyright 2025 Google LLC."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "apache",
   "metadata": {},
   "source": [
    "Licensed under the Apache License, Version 2.0 (the \"License\");\n",
    "you may not use this file except in compliance with the License.\n",
    "You may obtain a copy of the License at\n",
    "\n",
    "    http://www.apache.org/licenses/LICENSE-2.0\n",
    "\n",
    "Unless required by applicable law or agreed to in writing, software\n",
    "distributed under the License is distributed on an \"AS IS\" BASIS,\n",
    "WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.\n",
    "See the License for the specific language governing permissions and\n",
    "limitations under the License.\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "basename",
   "metadata": {},
   "source": [
    "# appointments"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "link",
   "metadata": {},
   "source": [
    "<table align=\"left\">\n",
    "<td>\n",
    "<a href=\"https://colab.research.google.com/github/google/or-tools/blob/main/examples/notebook/examples/appointments.ipynb\"><img src=\"https://raw.githubusercontent.com/google/or-tools/main/tools/colab_32px.png\"/>Run in Google Colab</a>\n",
    "</td>\n",
    "<td>\n",
    "<a href=\"https://github.com/google/or-tools/blob/main/examples/python/appointments.py\"><img src=\"https://raw.githubusercontent.com/google/or-tools/main/tools/github_32px.png\"/>View source on GitHub</a>\n",
    "</td>\n",
    "</table>"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "doc",
   "metadata": {},
   "source": [
    "First, you must install [ortools](https://pypi.org/project/ortools/) package in this colab."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "install",
   "metadata": {},
   "outputs": [],
   "source": [
    "%pip install ortools"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "description",
   "metadata": {},
   "source": [
    "\n",
    "Appointment selection.\n",
    "\n",
    "This module maximizes the number of appointments that can\n",
    "be fulfilled by a crew of installers while staying close to ideal\n",
    "ratio of appointment types.\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "code",
   "metadata": {},
   "outputs": [],
   "source": [
    "from ortools.sat.colab import flags\n",
    "from ortools.linear_solver import pywraplp\n",
    "from ortools.sat.python import cp_model\n",
    "\n",
    "\n",
    "_LOAD_MIN = flags.define_integer(\"load_min\", 480, \"Minimum load in minutes.\")\n",
    "_LOAD_MAX = flags.define_integer(\"load_max\", 540, \"Maximum load in minutes.\")\n",
    "_COMMUTE_TIME = flags.define_integer(\"commute_time\", 30, \"Commute time in minutes.\")\n",
    "_NUM_WORKERS = flags.define_integer(\"num_workers\", 98, \"Maximum number of workers.\")\n",
    "\n",
    "\n",
    "class AllSolutionCollector(cp_model.CpSolverSolutionCallback):\n",
    "    \"\"\"Stores all solutions.\"\"\"\n",
    "\n",
    "    def __init__(self, variables):\n",
    "        cp_model.CpSolverSolutionCallback.__init__(self)\n",
    "        self.__variables = variables\n",
    "        self.__collect = []\n",
    "\n",
    "    def on_solution_callback(self) -> None:\n",
    "        \"\"\"Collect a new combination.\"\"\"\n",
    "        combination = [self.value(v) for v in self.__variables]\n",
    "        self.__collect.append(combination)\n",
    "\n",
    "    def combinations(self) -> list[list[int]]:\n",
    "        \"\"\"Returns all collected combinations.\"\"\"\n",
    "        return self.__collect\n",
    "\n",
    "\n",
    "def enumerate_all_knapsacks_with_repetition(\n",
    "    item_sizes: list[int], total_size_min: int, total_size_max: int\n",
    ") -> list[list[int]]:\n",
    "    \"\"\"Enumerate all possible knapsacks with total size in the given range.\n",
    "\n",
    "    Args:\n",
    "      item_sizes: a list of integers. item_sizes[i] is the size of item #i.\n",
    "      total_size_min: an integer, the minimum total size.\n",
    "      total_size_max: an integer, the maximum total size.\n",
    "\n",
    "    Returns:\n",
    "      The list of all the knapsacks whose total size is in the given inclusive\n",
    "      range. Each knapsack is a list [#item0, #item1, ... ], where #itemK is an\n",
    "      nonnegative integer: the number of times we put item #K in the knapsack.\n",
    "    \"\"\"\n",
    "    model = cp_model.CpModel()\n",
    "    variables = [\n",
    "        model.new_int_var(0, total_size_max // size, \"\") for size in item_sizes\n",
    "    ]\n",
    "    load = sum(variables[i] * size for i, size in enumerate(item_sizes))\n",
    "    model.add_linear_constraint(load, total_size_min, total_size_max)\n",
    "\n",
    "    solver = cp_model.CpSolver()\n",
    "    solution_collector = AllSolutionCollector(variables)\n",
    "    # Enumerate all solutions.\n",
    "    solver.parameters.enumerate_all_solutions = True\n",
    "    # solve\n",
    "    solver.solve(model, solution_collector)\n",
    "    return solution_collector.combinations()\n",
    "\n",
    "\n",
    "def aggregate_item_collections_optimally(\n",
    "    item_collections: list[list[int]],\n",
    "    max_num_collections: int,\n",
    "    ideal_item_ratios: list[float],\n",
    ") -> list[int]:\n",
    "    \"\"\"Selects a set (with repetition) of combination of items optimally.\n",
    "\n",
    "    Given a set of collections of N possible items (in each collection, an item\n",
    "    may appear multiple times), a  given \"ideal breakdown of items\", and a\n",
    "    maximum number of collections, this method finds the optimal way to\n",
    "    aggregate the collections in order to:\n",
    "    - maximize the overall number of items\n",
    "    - while keeping the ratio of each item, among the overall selection, as close\n",
    "      as possible to a given input ratio (which depends on the item).\n",
    "    Each collection may be selected more than one time.\n",
    "\n",
    "    Args:\n",
    "      item_collections: a list of item collections. Each item collection is a list\n",
    "        of integers [#item0, ..., #itemN-1], where #itemK is the number of times\n",
    "        item #K appears in the collection, and N is the number of distinct items.\n",
    "      max_num_collections: an integer, the maximum number of item collections that\n",
    "        may be selected (counting repetitions of the same collection).\n",
    "      ideal_item_ratios: A list of N float which sums to 1.0: the K-th element is\n",
    "        the ideal ratio of item #K in the whole aggregated selection.\n",
    "\n",
    "    Returns:\n",
    "      A pair (objective value, list of pairs (item collection, num_selections)),\n",
    "      where:\n",
    "        - \"objective value\" is the value of the internal objective function used\n",
    "          by the MIP Solver\n",
    "        - Each \"item collection\" is an element of the input item_collections\n",
    "        - and its associated \"num_selections\" is the number of times it was\n",
    "          selected.\n",
    "    \"\"\"\n",
    "    solver = pywraplp.Solver.CreateSolver(\"SCIP\")\n",
    "    if not solver:\n",
    "        return []\n",
    "    n = len(ideal_item_ratios)\n",
    "    num_distinct_collections = len(item_collections)\n",
    "    max_num_items_per_collection = 0\n",
    "    for template in item_collections:\n",
    "        max_num_items_per_collection = max(max_num_items_per_collection, sum(template))\n",
    "    upper_bound = max_num_items_per_collection * max_num_collections\n",
    "\n",
    "    # num_selections_of_collection[i] is an IntVar that represents the number\n",
    "    # of times that we will use collection #i in our global selection.\n",
    "    num_selections_of_collection = [\n",
    "        solver.IntVar(0, max_num_collections, \"s[%d]\" % i)\n",
    "        for i in range(num_distinct_collections)\n",
    "    ]\n",
    "\n",
    "    # num_overall_item[i] is an IntVar that represents the total count of item #i,\n",
    "    # aggregated over all selected collections. This is enforced with dedicated\n",
    "    # constraints that bind them with the num_selections_of_collection vars.\n",
    "    num_overall_item = [\n",
    "        solver.IntVar(0, upper_bound, \"num_overall_item[%d]\" % i) for i in range(n)\n",
    "    ]\n",
    "    for i in range(n):\n",
    "        ct = solver.Constraint(0.0, 0.0)\n",
    "        ct.SetCoefficient(num_overall_item[i], -1)\n",
    "        for j in range(num_distinct_collections):\n",
    "            ct.SetCoefficient(num_selections_of_collection[j], item_collections[j][i])\n",
    "\n",
    "    # Maintain the num_all_item variable as the sum of all num_overall_item\n",
    "    # variables.\n",
    "    num_all_items = solver.IntVar(0, upper_bound, \"num_all_items\")\n",
    "    solver.Add(solver.Sum(num_overall_item) == num_all_items)\n",
    "\n",
    "    # Sets the total number of workers.\n",
    "    solver.Add(solver.Sum(num_selections_of_collection) == max_num_collections)\n",
    "\n",
    "    # Objective variables.\n",
    "    deviation_vars = [\n",
    "        solver.NumVar(0, upper_bound, \"deviation_vars[%d]\" % i) for i in range(n)\n",
    "    ]\n",
    "    for i in range(n):\n",
    "        deviation = deviation_vars[i]\n",
    "        solver.Add(\n",
    "            deviation >= num_overall_item[i] - ideal_item_ratios[i] * num_all_items\n",
    "        )\n",
    "        solver.Add(\n",
    "            deviation >= ideal_item_ratios[i] * num_all_items - num_overall_item[i]\n",
    "        )\n",
    "\n",
    "    solver.Maximize(num_all_items - solver.Sum(deviation_vars))\n",
    "\n",
    "    result_status = solver.Solve()\n",
    "\n",
    "    if result_status == pywraplp.Solver.OPTIMAL:\n",
    "        # The problem has an optimal solution.\n",
    "        return [int(v.solution_value()) for v in num_selections_of_collection]\n",
    "    return []\n",
    "\n",
    "\n",
    "def get_optimal_schedule(\n",
    "    demand: list[tuple[float, str, int]]\n",
    ") -> list[tuple[int, list[tuple[int, str]]]]:\n",
    "    \"\"\"Computes the optimal schedule for the installation input.\n",
    "\n",
    "    Args:\n",
    "      demand: a list of \"appointment types\". Each \"appointment type\" is a triple\n",
    "        (ideal_ratio_pct, name, duration_minutes), where ideal_ratio_pct is the\n",
    "        ideal percentage (in [0..100.0]) of that type of appointment among all\n",
    "        appointments scheduled.\n",
    "\n",
    "    Returns:\n",
    "      The same output type as EnumerateAllKnapsacksWithRepetition.\n",
    "    \"\"\"\n",
    "    combinations = enumerate_all_knapsacks_with_repetition(\n",
    "        [a[2] + _COMMUTE_TIME.value for a in demand],\n",
    "        _LOAD_MIN.value,\n",
    "        _LOAD_MAX.value,\n",
    "    )\n",
    "    print(\n",
    "        (\n",
    "            \"Found %d possible day schedules \" % len(combinations)\n",
    "            + \"(i.e. combination of appointments filling up one worker's day)\"\n",
    "        )\n",
    "    )\n",
    "\n",
    "    selection = aggregate_item_collections_optimally(\n",
    "        combinations, _NUM_WORKERS.value, [a[0] / 100.0 for a in demand]\n",
    "    )\n",
    "    output = []\n",
    "    for i, s in enumerate(selection):\n",
    "        if s != 0:\n",
    "            output.append(\n",
    "                (\n",
    "                    s,\n",
    "                    [\n",
    "                        (combinations[i][t], d[1])\n",
    "                        for t, d in enumerate(demand)\n",
    "                        if combinations[i][t] != 0\n",
    "                    ],\n",
    "                )\n",
    "            )\n",
    "\n",
    "    return output\n",
    "\n",
    "\n",
    "def main(_):\n",
    "    demand = [(45.0, \"Type1\", 90), (30.0, \"Type2\", 120), (25.0, \"Type3\", 180)]\n",
    "    print(\"*** input problem ***\")\n",
    "    print(\"Appointments: \")\n",
    "    for a in demand:\n",
    "        print(\"   %.2f%% of %s : %d min\" % (a[0], a[1], a[2]))\n",
    "    print(\"Commute time = %d\" % _COMMUTE_TIME.value)\n",
    "    print(\n",
    "        \"Acceptable duration of a work day = [%d..%d]\"\n",
    "        % (_LOAD_MIN.value, _LOAD_MAX.value)\n",
    "    )\n",
    "    print(\"%d workers\" % _NUM_WORKERS.value)\n",
    "    selection = get_optimal_schedule(demand)\n",
    "    print()\n",
    "    installed = 0\n",
    "    installed_per_type = {}\n",
    "    for a in demand:\n",
    "        installed_per_type[a[1]] = 0\n",
    "\n",
    "    print(\"*** output solution ***\")\n",
    "    for template in selection:\n",
    "        num_instances = template[0]\n",
    "        print(\"%d schedules with \" % num_instances)\n",
    "        for t in template[1]:\n",
    "            mult = t[0]\n",
    "            print(\"   %d installation of type %s\" % (mult, t[1]))\n",
    "            installed += num_instances * mult\n",
    "            installed_per_type[t[1]] += num_instances * mult\n",
    "\n",
    "    print()\n",
    "    print(\"%d installations planned\" % installed)\n",
    "    for a in demand:\n",
    "        name = a[1]\n",
    "        per_type = installed_per_type[name]\n",
    "        if installed != 0:\n",
    "            print(\n",
    "                f\"   {per_type} ({per_type * 100.0 / installed}%) installations of\"\n",
    "                f\" type {name} planned\"\n",
    "            )\n",
    "        else:\n",
    "            print(f\"   {per_type} installations of type {name} planned\")\n",
    "\n",
    "\n",
    "main()\n",
    "\n"
   ]
  }
 ],
 "metadata": {
  "language_info": {
   "name": "python"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}
